/*
 * SudokuBoard.java
 * Written by Guo Jiayuan U087174L
 * Last modified: 23/08/09
 */

import java.util.*;
import java.awt.Point;

//Class representing the sudoku board in a sudoku game
public class SudokuBoard {

	final static int BOARD_SIZE = 9;
	private Cell[][] cells;
	Stack<Cell[][]> stackOfCells;
	private boolean bruteForceStop;

	public SudokuBoard() {
		// Initialise the cells on the sudoku board
		// set its default possible values to '123456789'
		cells = new Cell[BOARD_SIZE][BOARD_SIZE];
		stackOfCells = new Stack<Cell[][]>();
		bruteForceStop = false;
		for (int r = 0; r < BOARD_SIZE; r++) {
			for (int c = 0; c < BOARD_SIZE; c++) {
				cells[r][c] = new Cell("0", "123456789");
			}
		}
	}

	// display the sudoku board
	public void printBoard() {
		System.out.println("     1 2 3   4 5 6   7 8 9");
		for (int r = 0; r < BOARD_SIZE; r++) {
			if (r % 3 == 0)
				System.out.println("   +-----------------------+");
			System.out.print(" " + (r + 1) + " ");
			for (int c = 0; c < BOARD_SIZE; c++) {
				if (c % 3 == 0)
					System.out.print("| ");
				System.out.print((cells[r][c].getValue().equals("0") ? " "
						: cells[r][c])
						+ " ");
			}
			System.out.println("|");
		}
		System.out.println("   +-----------------------+");
	} // end printBoard

	// check individual cells in the board from left to right,
	// top to bottom for a possible value to fill in
	public boolean chkRowsAndCols() throws Exception {
		String possibleValues = "";
		for (int r = 0; r < BOARD_SIZE; r++) {
			for (int c = 0; c < BOARD_SIZE; c++) {
				if (cells[r][c].getValue().equals("0")) {
					possibleValues = computePossibleValues(cells[r][c], r, c);
					if (possibleValues.length() == 1) {
						cells[r][c].setValue(possibleValues);
						return true;
					} else if (possibleValues.length() == 0)
						throw new Exception("Invalid placement.");
				}
			}
		}
		return false;
	}

	// copy the current state of the sudoku board to a new board
	private Cell[][] copyBoard() {
		Cell[][] copyCells = new Cell[BOARD_SIZE][BOARD_SIZE];
		for (int r = 0; r < BOARD_SIZE; r++) {
			for (int c = 0; c < BOARD_SIZE; c++) {
				copyCells[r][c] = new Cell(cells[r][c].getValue(), cells[r][c]
						.getPossibleValues());
			}
		}
		return copyCells;
	} // end copyBoard

	// 1st solving technique
	// find the list of possible numbers for the cell by checking
	// its grid, row and column. Update the cell with the list of
	// possible numbers.
	private String computePossibleValues(Cell cell, int row, int col) {

		String possibleValues = cell.getPossibleValues();
		// check the row of the cell
		for (int c = 0; c < BOARD_SIZE; c++) {
			if (!cells[row][c].getValue().equals("0"))
				possibleValues = possibleValues.replace(cells[row][c]
						.getValue(), "");
		}

		// check the col of the cell
		for (int r = 0; r < BOARD_SIZE; r++) {
			if (!cells[r][col].getValue().equals("0"))
				possibleValues = possibleValues.replace(cells[r][col]
						.getValue(), "");
		}

		// compute the starting row and col index of the minigrid
		int startRow = (row % 3 == 0) ? row : row - (row % 3);
		int startCol = (col % 3 == 0) ? col : col - (col % 3);

		// check the minigrid of the cell
		for (int r = startRow; r < startRow + 3; r++) {
			for (int c = startCol; c < startCol + 3; c++) {
				if (!cells[r][c].getValue().equals("0"))
					possibleValues = possibleValues.replace(cells[r][c]
							.getValue(), "");
			}
		}
		cell.setPossibleValues(possibleValues);
		return possibleValues;
	}

	// to check if the puzzle has been solved
	public boolean isPuzzleSolved() {
		String possibleValues;
		// check all rows of the board
		for (int r = 0; r < BOARD_SIZE; r++) {
			possibleValues = "123456789";
			for (int c = 0; c < BOARD_SIZE; c++) {
				possibleValues = possibleValues.replace(cells[r][c].getValue(),
						"");
			}
			if (possibleValues.length() > 0)
				return false;
		}
		// check all columns of the board
		for (int c = 0; c < BOARD_SIZE; c++) {
			possibleValues = "123456789";
			for (int r = 0; r < BOARD_SIZE; r++) {
				possibleValues = possibleValues.replace(cells[r][c].getValue(),
						"");
			}
			if (possibleValues.length() > 0)
				return false;
		}
		// check all minigrids of the board
		for (int i = 0; i < BOARD_SIZE; i++) {
			possibleValues = "123456789";
			int srow = (i % 3 == 0) ? i : i - (i % 3);
			int scol = (i % 3 == 0) ? i : (i % 3) * 3;
			for (int r = srow; r < srow + 3; r++) {
				for (int c = scol; c < scol + 3; c++) {
					possibleValues = possibleValues.replace(cells[r][c]
							.getValue(), "");
				}
			}
			if (possibleValues.length() > 0)
				return false;
		}
		return true;
	}

	// 2nd solving technique
	// compare the possible values of all the cells in the
	// same column and look for a unique number. If a unique
	// number exists, update the cell with that number
	public void chkLoneRangerInCol() {
	}

	public void chkLoneRangerInRow() {
	}

	public void chkLoneRangerInGrid() {
	}

	// this function randomize a given list of possible values
	private String randomizeValues(String possibleValues) {
		StringBuffer sb = new StringBuffer(possibleValues);
		for (int i = 0; i < sb.length(); i++) {
			int rnd = (int) ((sb.length() - i + 1) * Math.random() + i)
					% sb.length();
			char temp = sb.charAt(i);
			sb.setCharAt(i, sb.charAt(rnd));
			sb.setCharAt(rnd, temp);
		}
		return sb.toString();
	}

	// find cell with least number of possible of values
	private Point findCellWLeastPossibleVal() {
		int min = BOARD_SIZE;
		int row = 0, col = 0;
		for (int r = 0; r < BOARD_SIZE; r++) {
			for (int c = 0; c < BOARD_SIZE; c++) {
				if (cells[r][c].getValue().equals("0")
						&& cells[r][c].getPossibleValues().length() < min) {
					min = cells[r][c].getPossibleValues().length();
					row = r;
					col = c;
				}
			}
		}
		return new Point(row, col);
	}

	// create a new Sudoku puzzle
	public void createNewGame(int level) {
		int noOfEmptyCells = 0;
		switch (level) {
		case 1:
			noOfEmptyCells = (int) (Math.random() * 6) + 40;
			break;
		case 2:
			noOfEmptyCells = (int) (Math.random() * 4) + 46;
			break;
		case 3:
			noOfEmptyCells = (int) (Math.random() * 4) + 50;
			break;
		case 4:
			noOfEmptyCells = (int) (Math.random() * 5) + 54;
		}
		this.stackOfCells.clear();
		this.solveByBruteForce();
		this.createEmptyCells(noOfEmptyCells);
		try {
			this.chkRowsAndCols();
		} catch (Exception ex) {
		}
		this.printBoard();
	}

	// solving the puzzle by placing a random number
	// from the list of possible values of the cell
	public void solveByBruteForce() {
		Point pos = findCellWLeastPossibleVal();
		String possibleValues = cells[pos.x][pos.y].getPossibleValues();
		possibleValues = randomizeValues(possibleValues);
		// save the original state of the board into a stack for backtracking
		stackOfCells.push(copyBoard());

		for (int i = 0; i < possibleValues.length(); i++) {
			cells[pos.x][pos.y].setValue(Character.toString(possibleValues
					.charAt(0)));
			try {
				if (solvePuzzle()) {
					bruteForceStop = true;
					return;
				} else {
					solveByBruteForce();
					if (bruteForceStop)
						return;
				}
			} catch (Exception ex) {
				// System.out.println(ex);
				cells = stackOfCells.pop();
			}
		}
	}

	// create random number of empty cells base on the puzzle diffculty
	public void createEmptyCells(int noOfEmptyCells) {
		int row = 0, col = 0;
		for (int i = 0; i < (noOfEmptyCells / 2); i++) {
			boolean isEmpty;
			do {
				isEmpty = false;
				// get a cell in the first half of the board
				do {
					row = (int) (Math.random() * 5);
					col = (int) (Math.random() * 9);
				} while (row == 4 && col > 4);

				if (cells[row][col].getValue().equals("0"))
					isEmpty = true;

				if (!isEmpty) {
					// reset the cell to default state
					cells[row][col].setValue("0");
					cells[row][col].setPossibleValues("123456789");
					// reflect the top half of the board to make it symmetrical
					cells[8 - row][8 - col].setValue("0");
					cells[8 - row][8 - col].setPossibleValues("123456789");
				}
			} while (isEmpty);
		}
	}

	// solve the puzzle by using several logical techniques
	// and brute force method if all logical techniques had failed
	// to solve the puzzle.
	public boolean solvePuzzle() throws Exception {
		boolean isConfirmed = false;
		do {
			isConfirmed = chkRowsAndCols();
			if (isPuzzleSolved())
				return true;
		} while (isConfirmed);
		return false;
	}
} // end class SudokuBoard